Policies

  • Tue 25 Oct 2016, 13:10 - 14:30
  • Allowed:
    • Paper copy of textbook
    • Paper notes, printed or handwritten
    • Please bring your own blank white 8.5x11” paper
  • Not allowed:
    • Use of electronics, computers, etc. (all screens off)
    • Use of mobile phone (off/mute and in pocket/bag)
    • Sharing of textbook, notes, etc.
  • If you feel a question is ambiguous, write on your exam sheet your interpretation of the question, and answer accordingly.
  • Please label/number your pages clearly and staple them in order when handing in.

Midterm Exam (60pts) (solutions)

  1. (3pts) : Prove or disprove: if `f in O(g(n))` and `g in O(f(n))`, then `f=g`

    Solution: False: a counterexample is `f(n)=n` and `g(n)=2n`.

  2. (4pts) : Prove: `n^10 e^n in o(3^n)`

    Solution: Apply log (e.g., ln) to both sides (monotonic):
    We want to show `10 ln n + n in o(n ln 3) = o(n)`.
    Use limit definition of o(): `lim_(n->oo) (10 ln n + n)/n` = `lim_(n->oo) (10 ln n)/n + 1` = 0 (e.g., by applying L'Hôpital's rule)

  3. (6pts): Prove from definition: `n^2 + O(n log n) = O(n^2)`

    Solution: Let `f in O(n log n)`, i.e., let `c_0, n_0` be such that `forall n > n_0, f(n) <= c_0 n log n`.
    Since n > log n, we can let `n_1=n_0` and `c_1=1+c_0`, and we have `forall n > n_0`
    `n^2 + f(n) <= n^2 + c_0 n log n` `<= n^2 + c_0 n^2` `= (1+c_0)n^2 = c_1 n^2`,
    which proves the result.

  4. (6pts): Prove by induction, for all n ≥ 1: `sum_(k=1)^n k(k!) = (n+1)!-1`

    Solution: Base case: `sum_(k=1)^1 k(k!) = 1(1!) = 1 = 2-1 = (1+1)!-1`.
    Inductive step: `sum_(k=1)^n k(k!)` = `n(n!)+sum_(k=1)^(n-1) k(k!)` (pulling out one term)
    = `n(n!) + (n!)-1` (by inductive hypothesis at n-1)
    = `n!(n+1)-1` (factor out n!)
    = `(n+1)!-1`.

  5. (5pts): We have now learned 7 sorting algorithms: insertion, merge, heap, quick, counting, radix, bucket. For each, briefly summarise the pros/cons, assumptions, and key features.

    Solution:
    Insertion: Easy to code, fast on "approximately sorted" input, but average case slow `Theta(n^2)`
    Merge: Always Θ(n lg n), but requires copying
    Heap: Also Θ(n lg n), but often more swaps than Quicksort
    Quick: Average/random case Θ(n lg n), worst case `Theta(n^2)`, few swaps on real-world input
    Counting: Assumes items can only take on a small number k of values. Out-of-place but stable. Θ(n+k)
    Radix: Assumes items can be split into digits. Depends on a fast, stable sort like counting sort. Θ(d(n+k)), depends on choice of radix (i.e., how to split into digits)
    Bucket: Assumes values uniformly distributed in [0,1)

  6. (8pts): Demonstrate QuickSort (Lomuto partitioning, non-randomised) on the following input: [ M T K D S F G L ]. How many (non-trivial) swaps?

    Solution: Each line is just after a non-trivial swap (9 total).

    lohipivsplcur MTKD SFGL
    18L13 KTMD SFGL
    18L24 KDMT SFGL
    18L36 KDFT SMGL
    18L47 KDFG SMTL
    18L5- KDFG LMTS
    14G12 DKFG LMTS
    14G23 DFKG LMTS
    14G3- DFGK LMTS
    68S7- DFGK LMST

  7. (6pts): Consider an array of 2D points `{(x_i, y_i)}_(i=1)^n` uniformly distributed within the unit disk (i.e., inside the circle of radius 1 centered at (0,0)).
    Describe in words how you might efficiently sort this array in increasing order of distance from the origin (0,0).

    Solution: The critical thing to notice is that the points are not uniformly distributed in terms of distance from the origin.

    One way to see this is by considering annular rings of fixed width dr, e.g., `{(x,y): r < sqrt(x^2+y^2) < r+dr}`. The area of the ring is `pi(r+dr)^2-pi r^2` = `2pi r dr + pi (dr)^2`, which increases linearly with r.

    From this, we can see that if we use the square of the distance as the key to determine buckets, rather than just the distance, then it is equivalent to dividing the unit disk into annular rings of equal area:
    Each ring is `{(x,y): h < x^2+y^2 < h+dh}` = `{(x,y): sqrt(h) < sqrt(x^2+y^2) < sqrt(h+dh)}`.
    The area of each ring is `pi(sqrt(h+dh))^2 - pi(sqrt(h))^2` = `pi(r+dr) - pi(r)` = `pi dr`, which is constant.

    So the solution is to use bucket sort on the square of the distance from the origin.

  8. (8pts): Demonstrate inserting the input [ 7, 11, 16, 22, 36 ] into a hash-table of size m=5, using

    • (a) division hash,
    • (b) division hash and linear probing, and
    • (c) division hash and quadratic probing with `c_1=0.5, c_2=2.5` (round the result down).

    bkt: 0 1 2 3 4
    key: 711162236
    mod5 2 1 1 2 1
    div -11 7 - -
    - -1622 - -
    - -36 - - -
    lin 3611 71622
    quad2211 73616

  9. (8pts): Identify the problem(s) in the following pseudocode for deleting a node from a singly-linked list.
    Fix it (i.e, rewrite delete()). Assume reasonable class definitions of LinkedList and Node. 

    class LinkedList:
  def delete( self, key ):
    node = self.search( key )
    if (!node): return			# key not in list
    if node == self.head:
      self.head = node.next
    del node

    Solution: The next pointer in the previous node needs to be updated to skip over the node to be deleted. But since we are a singly-linked list and search brought us too far already, we can't do that. We need to extend the code for search:

    def delete( self, key ):
  if self.head == None: return		# empty list
  if key == self.head.key:		# del head
    cur = self.head
    self.head = cur.next
    del cur
    return
  prev = self.head			# search for key
  cur = prev.next
  while cur != None:
    if cur.key == key:			# del cur node
      prev.next = cur.next
      del cur
      return
    prev = cur
    cur = cur.next

  10. (6pts): Reconstruct the binary search tree whose post-order traversal is D H M K F T X V R Y Q.

    Solution: